package algorithms.question.class14;

import common.bean.TreeNode;
import common.util.MyUtil;

/**
 * 给定一个棵完全二叉树，
 * 返回这棵树的节点个数，
 * 要求时间复杂度小于O(树的节点数)
 *
 * @author guichang
 * @date 2021/8/11
 */

@SuppressWarnings("all")
public class Code4_完全二叉树的节点个数 {

    public static void main(String[] args) {
        TreeNode treeNode = MyUtil.createTreeNode(1, 2, 3, 4, 5, 6, 7);
        MyUtil.print(countNodes(treeNode));
    }

    public static int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int maxLevel = mostLeftLevel(root, 1);
        return treeNums(root, 1, maxLevel);
    }

    /**
     * head完全二叉树的节点个数
     *
     * @param head      二叉树的头节点
     * @param currLevel 当前层数
     * @param maxLevel  最大层数
     * @return 节点数
     */
    private static int treeNums(TreeNode head, int currLevel, int maxLevel) {
        // 当前来到了最后一层
        if (currLevel == maxLevel) {
            return 1;
        }
        // 右树高度等于最大高度表示左树是满的，否则右树满的
        int rightLevel = mostLeftLevel(head.right, currLevel + 1);
        if (rightLevel == maxLevel) {
            return (1 << (maxLevel - currLevel)) + treeNums(head.right, currLevel + 1, maxLevel);
        } else {
            return (1 << (maxLevel - currLevel - 1)) + treeNums(head.left, currLevel + 1, maxLevel);
        }
    }

    /**
     * 以head为头的二叉树的最左节点在第几层
     *
     * @param head  头节点
     * @param level 当前层数
     * @return 最左节点在第几层
     */
    private static int mostLeftLevel(TreeNode head, int level) {
        TreeNode temp = head;
        while (temp != null) {
            level++;
            temp = temp.left;
        }
        return level - 1;
    }

}